Лемма о циклах

Для любого графа $G$, $e$ — мост $\iff e$ не содержится ни в одном цикле $G$.

**Необходимость:** Если $e$ содержится в некотором цикле, то по лемме о разрыве цикла, графы $G-e$ и $G$ имеют одни и те же компоненты связности. Следовательно, $e$ не является мостом. По правилу контрапозиции, если $e$ — мост, то он не содержится ни в одном цикле. **Достаточность:** Пусть $e=(u,v)$ не содержится ни в одном цикле. Если в $G-e$ есть $(u,v)$-цепь, то эта цепь вместе с ребром $e$ образует цикл, что невозможно. Значит, вершины $u$ и $v$ лежат в разных компонентах связности графа $G-e$, но в одной компоненте связности в $G$ благодаря ребру $e$. Следовательно, число компонент связности при удалении $e$ увеличилось, а значит $e$ — мост. $\square$